import java.util.*;

/**
 * 题目：生成哈夫曼树
 * 
 * 题目描述：
 * 根据给定的无序数值数组，构造哈夫曼树，并输出哈夫曼树的中序遍历。
 * 
 * 为了确保中序遍历输出的一致性，添加以下限制：
 * - 在任意二叉树节点中，左子节点的权值必须小于等于右子节点的权值
 * - 根节点的权值为左右子节点权值之和
 * - 如果左右子节点权值相等，左子树的高度必须小于等于右子树的高度
 * 
 * 注意：所有测试用例都保证有效，能够生成哈夫曼树。
 * 
 * 提示：哈夫曼树也称为最优二叉树，是带权路径长度最短的二叉树。
 * 树的带权路径长度为所有叶子节点的权值乘以其到根节点的路径长度之和。
 * 
 * 输入描述：
 * 第一行输入为数组长度，记为N，1<=N<=1000，第二行输入无序数值数组，以空格分割，数值均大于等于1，小于100000。
 * 
 * 输出描述：
 * 输出一个哈夫曼树的中序遍历的数组，数值间以空格分割。
 * 
 * 示例1：
 * 输入：
 * 5
 * 5 15 40 30 10
 * 输出：
 * 40 100 30 60 15 30 5 15 10
 * 
 * 解题思路：
 * 哈夫曼树的构造过程：
 * 1. 将所有权值作为叶子节点，放入优先队列（最小堆）
 * 2. 重复以下步骤直到队列中只剩一个节点：
 *    - 取出两个权值最小的节点
 *    - 创建一个新节点，权值为两个子节点权值之和
 *    - 将新节点放回队列
 * 3. 最后剩余的节点就是根节点
 * 4. 对构造的树进行中序遍历
 * 
 * 算法分析：
 * - 时间复杂度：O(n log n)
 * - 空间复杂度：O(n)
 * - 算法类型：贪心算法，优先队列
 */
public class HuffmanTreeGeneration {
    
    // 哈夫曼树节点定义
    static class HuffmanNode {
        int weight;
        HuffmanNode left;
        HuffmanNode right;
        int height; // 用于处理权值相等时的高度比较
        
        public HuffmanNode(int weight) {
            this.weight = weight;
            this.left = null;
            this.right = null;
            this.height = 0;
        }
        
        public HuffmanNode(int weight, HuffmanNode left, HuffmanNode right) {
            this.weight = weight;
            this.left = left;
            this.right = right;
            this.height = Math.max(left.height, right.height) + 1;
        }
    }
    
    /**
     * 方法1：优先队列法（推荐使用）
     * 使用PriorityQueue实现哈夫曼树构造，效率最高
     * 
     * 算法思路：
     * 1. 将所有叶子节点放入优先队列（按权值排序）
     * 2. 每次取出两个权值最小的节点合并
     * 3. 将合并后的节点放回队列
     * 4. 重复直到队列中只剩一个节点
     * 
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     */
    public static List<Integer> buildHuffmanTree1(int[] weights) {
        if (weights.length == 1) {
            return Arrays.asList(weights[0]);
        }
        
        // 创建优先队列，按权值排序，权值相等时按高度排序
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>((a, b) -> {
            if (a.weight != b.weight) {
                return Integer.compare(a.weight, b.weight);
            }
            return Integer.compare(a.height, b.height);
        });
        
        // 将所有叶子节点加入队列
        for (int weight : weights) {
            pq.offer(new HuffmanNode(weight));
        }
        
        // 构造哈夫曼树
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            
            // 确保左子节点权值小于等于右子节点权值
            if (left.weight > right.weight || 
                (left.weight == right.weight && left.height > right.height)) {
                HuffmanNode temp = left;
                left = right;
                right = temp;
            }
            
            HuffmanNode parent = new HuffmanNode(left.weight + right.weight, left, right);
            pq.offer(parent);
        }
        
        // 中序遍历
        List<Integer> result = new ArrayList<>();
        inorderTraversal(pq.poll(), result);
        return result;
    }
    
    /**
     * 方法2：数组排序法
     * 使用数组排序和手动合并实现哈夫曼树构造
     * 
     * 算法思路：
     * 1. 将权值数组排序
     * 2. 手动维护一个节点列表
     * 3. 每次找到两个权值最小的节点合并
     * 
     * 时间复杂度：O(n² log n)
     * 空间复杂度：O(n)
     */
    public static List<Integer> buildHuffmanTree2(int[] weights) {
        if (weights.length == 1) {
            return Arrays.asList(weights[0]);
        }
        
        List<HuffmanNode> nodes = new ArrayList<>();
        for (int weight : weights) {
            nodes.add(new HuffmanNode(weight));
        }
        
        // 构造哈夫曼树
        while (nodes.size() > 1) {
            // 按权值排序，权值相等时按高度排序
            nodes.sort((a, b) -> {
                if (a.weight != b.weight) {
                    return Integer.compare(a.weight, b.weight);
                }
                return Integer.compare(a.height, b.height);
            });
            
            HuffmanNode left = nodes.remove(0);
            HuffmanNode right = nodes.remove(0);
            
            // 确保左子节点权值小于等于右子节点权值
            if (left.weight > right.weight || 
                (left.weight == right.weight && left.height > right.height)) {
                HuffmanNode temp = left;
                left = right;
                right = temp;
            }
            
            HuffmanNode parent = new HuffmanNode(left.weight + right.weight, left, right);
            nodes.add(parent);
        }
        
        // 中序遍历
        List<Integer> result = new ArrayList<>();
        inorderTraversal(nodes.get(0), result);
        return result;
    }
    
    /**
     * 方法3：递归构造法
     * 使用递归方式构造哈夫曼树
     * 
     * 算法思路：
     * 1. 递归地将数组分成两部分
     * 2. 分别构造左右子树
     * 3. 合并成新的节点
     * 
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     */
    public static List<Integer> buildHuffmanTree3(int[] weights) {
        if (weights.length == 1) {
            return Arrays.asList(weights[0]);
        }
        
        Arrays.sort(weights);
        HuffmanNode root = buildHuffmanTreeRecursive(weights, 0, weights.length - 1);
        
        List<Integer> result = new ArrayList<>();
        inorderTraversal(root, result);
        return result;
    }
    
    private static HuffmanNode buildHuffmanTreeRecursive(int[] weights, int start, int end) {
        if (start == end) {
            return new HuffmanNode(weights[start]);
        }
        
        if (start + 1 == end) {
            return new HuffmanNode(weights[start] + weights[end], 
                                 new HuffmanNode(weights[start]), 
                                 new HuffmanNode(weights[end]));
        }
        
        // 找到分割点，使得左右两部分权值尽可能接近
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += weights[i];
        }
        
        int halfSum = sum / 2;
        int currentSum = 0;
        int split = start;
        
        for (int i = start; i <= end; i++) {
            currentSum += weights[i];
            if (currentSum >= halfSum) {
                split = i;
                break;
            }
        }
        
        HuffmanNode left = buildHuffmanTreeRecursive(weights, start, split);
        HuffmanNode right = buildHuffmanTreeRecursive(weights, split + 1, end);
        
        return new HuffmanNode(left.weight + right.weight, left, right);
    }
    
    /**
     * 方法4：堆优化法
     * 使用自定义堆实现哈夫曼树构造
     * 
     * 算法思路：
     * 1. 实现一个最小堆
     * 2. 使用堆来维护节点
     * 3. 每次取出两个最小节点合并
     * 
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     */
    public static List<Integer> buildHuffmanTree4(int[] weights) {
        if (weights.length == 1) {
            return Arrays.asList(weights[0]);
        }
        
        // 使用自定义最小堆
        MinHeap heap = new MinHeap(weights.length);
        for (int weight : weights) {
            heap.insert(new HuffmanNode(weight));
        }
        
        // 构造哈夫曼树
        while (heap.size() > 1) {
            HuffmanNode left = heap.extractMin();
            HuffmanNode right = heap.extractMin();
            
            // 确保左子节点权值小于等于右子节点权值
            if (left.weight > right.weight || 
                (left.weight == right.weight && left.height > right.height)) {
                HuffmanNode temp = left;
                left = right;
                right = temp;
            }
            
            HuffmanNode parent = new HuffmanNode(left.weight + right.weight, left, right);
            heap.insert(parent);
        }
        
        // 中序遍历
        List<Integer> result = new ArrayList<>();
        inorderTraversal(heap.extractMin(), result);
        return result;
    }
    
    /**
     * 方法5：贪心算法法
     * 使用贪心策略构造哈夫曼树
     * 
     * 算法思路：
     * 1. 每次选择权值最小的两个节点
     * 2. 使用贪心策略确保最优解
     * 3. 维护节点的层次信息
     * 
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     */
    public static List<Integer> buildHuffmanTree5(int[] weights) {
        if (weights.length == 1) {
            return Arrays.asList(weights[0]);
        }
        
        // 使用TreeSet来维护节点，自动排序
        TreeSet<HuffmanNode> nodeSet = new TreeSet<>((a, b) -> {
            if (a.weight != b.weight) {
                return Integer.compare(a.weight, b.weight);
            }
            if (a.height != b.height) {
                return Integer.compare(a.height, b.height);
            }
            return Integer.compare(a.hashCode(), b.hashCode()); // 确保唯一性
        });
        
        for (int weight : weights) {
            nodeSet.add(new HuffmanNode(weight));
        }
        
        // 构造哈夫曼树
        while (nodeSet.size() > 1) {
            HuffmanNode left = nodeSet.pollFirst();
            HuffmanNode right = nodeSet.pollFirst();
            
            // 确保左子节点权值小于等于右子节点权值
            if (left.weight > right.weight || 
                (left.weight == right.weight && left.height > right.height)) {
                HuffmanNode temp = left;
                left = right;
                right = temp;
            }
            
            HuffmanNode parent = new HuffmanNode(left.weight + right.weight, left, right);
            nodeSet.add(parent);
        }
        
        // 中序遍历
        List<Integer> result = new ArrayList<>();
        inorderTraversal(nodeSet.pollFirst(), result);
        return result;
    }
    
    /**
     * 中序遍历辅助方法
     */
    private static void inorderTraversal(HuffmanNode root, List<Integer> result) {
        if (root == null) return;
        
        inorderTraversal(root.left, result);
        result.add(root.weight);
        inorderTraversal(root.right, result);
    }
    
    /**
     * 自定义最小堆实现
     */
    static class MinHeap {
        private HuffmanNode[] heap;
        private int size;
        private int capacity;
        
        public MinHeap(int capacity) {
            this.capacity = capacity;
            this.heap = new HuffmanNode[capacity];
            this.size = 0;
        }
        
        public void insert(HuffmanNode node) {
            if (size >= capacity) return;
            
            heap[size] = node;
            int current = size;
            size++;
            
            // 向上调整
            while (current > 0) {
                int parent = (current - 1) / 2;
                if (compare(heap[current], heap[parent]) < 0) {
                    swap(current, parent);
                    current = parent;
                } else {
                    break;
                }
            }
        }
        
        public HuffmanNode extractMin() {
            if (size == 0) return null;
            
            HuffmanNode min = heap[0];
            heap[0] = heap[size - 1];
            size--;
            
            // 向下调整
            int current = 0;
            while (true) {
                int left = 2 * current + 1;
                int right = 2 * current + 2;
                int smallest = current;
                
                if (left < size && compare(heap[left], heap[smallest]) < 0) {
                    smallest = left;
                }
                if (right < size && compare(heap[right], heap[smallest]) < 0) {
                    smallest = right;
                }
                
                if (smallest != current) {
                    swap(current, smallest);
                    current = smallest;
                } else {
                    break;
                }
            }
            
            return min;
        }
        
        public int size() {
            return size;
        }
        
        private int compare(HuffmanNode a, HuffmanNode b) {
            if (a.weight != b.weight) {
                return Integer.compare(a.weight, b.weight);
            }
            return Integer.compare(a.height, b.height);
        }
        
        private void swap(int i, int j) {
            HuffmanNode temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }
    }
    
    /**
     * 主方法 - 程序入口
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        System.out.println("请输入数组长度N：");
        int n = scanner.nextInt();
        
        System.out.println("请输入" + n + "个权值（空格分隔）：");
        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = scanner.nextInt();
        }
        
        // 测试所有方法
        System.out.println("\n=== 所有算法结果对比 ===");
        
        List<Integer> result1 = buildHuffmanTree1(weights);
        System.out.println("方法1（优先队列法）: " + result1);
        
        List<Integer> result2 = buildHuffmanTree2(weights);
        System.out.println("方法2（数组排序法）: " + result2);
        
        List<Integer> result3 = buildHuffmanTree3(weights);
        System.out.println("方法3（递归构造法）: " + result3);
        
        List<Integer> result4 = buildHuffmanTree4(weights);
        System.out.println("方法4（堆优化法）: " + result4);
        
        List<Integer> result5 = buildHuffmanTree5(weights);
        System.out.println("方法5（贪心算法法）: " + result5);
        
        // 推荐使用的方法
        System.out.println("\n推荐使用方法1（优先队列法），时间复杂度最优：O(n log n)");
        
        scanner.close();
    }
}
